package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Assert;
import org.junit.Test;

import java.util.Stack;

/**
 * @Date 2022/2/16 15:15
 * @Created by biubiu
 * @Link {https://leetcode-cn.com/problems/aMhZSa/}
 */
public class 回文链表 {


    @Test
    public void test() {//
        boolean palindrome = isPalindrome(ListNode.build(1, 2, 2, 1)); //2 null
        // boolean palindrome2 = isPalindrome(ListNode.build(1, 2, 3, 2,1)); 2 //1
        Assert.assertTrue(palindrome);
    }


    public boolean isPalindrome(ListNode head) {

        Stack<ListNode> prevPartNode = new Stack();
        if (head.next == null) {
            return true;
        }
        ListNode lastPartNode = null;
        ListNode slow = head;
        ListNode fast = head;
        prevPartNode.add(slow);

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            prevPartNode.add(slow);
        }
        if (fast.next != null){
            lastPartNode = slow.next;
        }else{
            ListNode midNode = prevPartNode.pop();
            lastPartNode = midNode.next;
        }


        while (!prevPartNode.isEmpty()) {
            ListNode stackNode = prevPartNode.pop();
            if (stackNode.val != lastPartNode.val) {
                return false;
            } else {
                lastPartNode = lastPartNode.next;
            }
        }
        return true;
    }


}
